package leetcode.D900.T877;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-22 18:48:10 星期二
 */
class Solution {

    static class ScorePair {
        int first;
        int second;

        public ScorePair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        ScorePair[][] dp = new ScorePair[n][n];
        for(int i=0; i<n; ++i)
            dp[i][i] = new ScorePair(piles[i], 0);
        for(int step=1; step<n; ++step) {
            for(int i=0; i<n-step; ++i) {
                int j = i + step;
                int a = dp[i][j-1].second + piles[j];
                int b = dp[i+1][j].second + piles[i];
                if (a >= b)
                    dp[i][j] = new ScorePair(a, dp[i][j-1].first);
                else
                    dp[i][j] = new ScorePair(b, dp[i + 1][j].first);
            }
        }
        return dp[n-1][n-1].first > dp[n-1][n-1].second;
    }
}
